class Solution(object):
    def regionsBySlashes(self, grid):
        m = len(grid)
        n = len(grid[0])
        index = 0
        d = {}
        for i in range(m):
            for j in range(n):
                if grid[i][j] == ' ':
                    d[(i, j, 0)] = index
                    index += 1
                if grid[i][j] == '/':
                    d[(i, j, 1)] = index
                    index += 1
                    d[(i, j, 2)] = index
                    index += 1
                if grid[i][j] == '\\':
                    d[(i, j, 3)] = index
                    index += 1
                    d[(i, j, 4)] = index
                    index += 1
        self.t = len(d)
        p = [i for i in range(self.t)]

        def find(x):
            if p[x] == x:
                return x
            else:
                p[x] = find(p[x])
                return p[x]

        def union(x, y):
            rootx = find(x)
            rooty = find(y)
            if rootx != rooty:
                if rootx < rooty:
                    p[rooty] = rootx
                else:
                    p[rootx] = rooty
                self.t -= 1

        for i, j, state in d:
            if i < m - 1:
                if state in {0, 2, 4}:
                    if (i + 1, j, 0) in d:
                        union(d[(i, j, state)], d[(i + 1, j, 0)])
                    if (i + 1, j, 1) in d:
                        union(d[(i, j, state)], d[(i + 1, j, 1)])
                    if (i + 1, j, 3) in d:
                        union(d[(i, j, state)], d[(i + 1, j, 3)])
            if j < n - 1:
                if state in {0, 2, 3}:
                    if (i, j + 1, 0) in d:
                        union(d[(i, j, state)], d[(i, j + 1, 0)])
                    if (i, j + 1, 1) in d:
                        union(d[(i, j, state)], d[(i, j + 1, 1)])
                    if (i, j + 1, 4) in d:
                        union(d[(i, j, state)], d[(i, j + 1, 4)])
        return self.t

data = Solution()
grid = ["/\\", "\\/"]
print(data.regionsBySlashes(grid))
grid = ["/ "]
print(data.regionsBySlashes(grid))